#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <algorithm>

using namespace std;

class quickSort
{
public:
	quickSort();
	~quickSort();
	static size_t retPos(int L,int R)
	{
		static default_random_engine e(time(0));
		static uniform_real_distribution<> u(0,1);
		return L+(int)((R-L+1)*u(e));
	}
	static void swap_Quicksort(std::vector<int>& v,size_t oldpos,size_t newpos){
		std::vector<int>::value_type temp;
		temp = v[oldpos];
		v[oldpos] = v[newpos];
		v[newpos] = temp;
	}
	static vector<int> partition(std::vector<int>& v,size_t L,size_t R){
			int less = L-1;
			int more = R;
			while(L<more)
			{
				/* code */
				if (v[L]<v[R])
				{
					swap_Quicksort(v,++less,L++);
				}
				else if(v[L]>v[R])
				{
					swap_Quicksort(v,--more,L);
				}
				else{
					++L;
				}
			}
			swap_Quicksort(v,R,more);
			std::vector<int> poisition = {less+1,more};
			return poisition;
	}
	static void sort(std::vector<int>&v,int low,int high){
		if (low<high)
		{
			/* code */
			int pos = retPos(low,high);//随机化的快速排序算法，在工程上使用
			swap_Quicksort(v,pos,high);
			std::vector<int> p = partition(v,low,high);//解决荷兰波西问题，利用partition函数将元素分成三个部分
			sort(v,low,p[0]-1);//low---->p[0]-1,小于尾元素的元素
			sort(v,p[1]+1,high);//p[1]+1-------->high,大于尾元素的数
		}
	}
};
class Comparator 
{
public:
	std::vector<int> geneArr()
	{
		static default_random_engine e(time(0));
		static uniform_int_distribution<int> u(1,10);//设个小的，进行人工计算
		std::vector<int> v;
		for(size_t i=0;i<7;i++){
		v.push_back(u(e));
		}
		return v;
	}
	void operator()(){
		std::vector<int> array1 = geneArr();
		std::vector<int> array2(array1);
		for(auto value:array2){
			cout<<value<<" ";
		}
		cout<<endl;
		cout<<"--------------------------"<<endl;
		cout<<"STL sort："<<endl;
		sort(array1.begin(),array1.end());
		for_each(array1.begin(),array1.end(),[](int val){cout<<val<<" ";});
		cout<<endl;
		cout<<"quickSort::sort："<<endl;
		quickSort::sort(array2,0,array2.size()-1);
		for_each(array2.begin(),array2.end(),[](int val){cout<<val<<" ";});
		cout<<endl;
	}
};

int main(){
	Comparator com;
	com();
	return 0;
}


